// https://leetcode.cn/problems/maximum-subarray/description/


// 以i位置的元素结尾的连续数组能获得的最大的值

function maxSubArray(nums: number[]):number {
    const n = nums.length;
    // 1.定义状态
    const dp: number[] = [];
    let preSum = nums[0]
    // 2.初始化状态
   let max =  preSum;
    // 3.状态转移方程
    for(let i = 1; i < n; i++) { 
        // 拿到当前数组的值和之前的最大值，如果之前的最大值是正数，则将当前值和之前的值进行相加，
        // 如果之前是负的，则当前值就是当前位置的最大连续数组的和,因为当前值也有可能是负的，所以选出更大的值更严谨
        // 
        // preValue = Math.max(nums[i] + preValue , nums[i]);
        // 当前的值
        const value1 = nums[i];
        // 当前的值加上前一个值
        const value2 = nums[i] + preSum;
        // 当前的值和前一个值进行对比,下面的这个preSum是最后一个值，将每次的值都和之前的最大值进行对比，存最大的
        preSum = Math.max(value2,value1)
        // 这里是更新最大值的
        max = Math.max(max,preSum)
    }
    // console.log(dp)
    // 4.返回出结果
    return max;
}
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

export default {};